ftp.cs.arizona.edu/ftp.cs.arizona.edu.tar/ftp.cs.arizona.edu/tsql/doc/tsql.mail/[e-mail] _Sun Apr 4 22:57:12 1993.msg

Internet Message Format | 1996-01-31 | 18KB

Received: from iesd.auc.dk by optima.cs.arizona.edu (5.65c/15) via SMTP
    id AA13248; Sun, 4 Apr 1993 13:57:35 MST
Received: from yellow.iesd.auc.dk by iesd.auc.dk with SMTP id AA14985
  (5.65c8/IDA-1.5/MD for <[e-mail]>); Sun, 4 Apr 1993 22:57:12 +0200
Date: Sun, 4 Apr 1993 22:57:12 +0200
From: "Christian S. Jensen" <[e-mail]>
Message-Id: <[e-mail]>
To: [e-mail]
Subject: TSQL benchmark

********************************************************************
*                  The TSQL Benchmark Initiative                   *
********************************************************************

Below, I have included the up-to-date version of the benchmark
document. The document now contains both the consensus schema and a
straw proposal for a database instance. In addition, I comment on the
most recent comments for improving the benchmark document. First,
however, there is a summary of the current status.

Best regards,
Christian

********************************************************************
*               Status for the three initial tasks.           *
********************************************************************

Task 1: The benchmark database schema.

There has now been several iterations, and many improvements over the
initial proposal have been suggested. (Below, I briefly discuss how I
have tried to reflect the most recent comments in the benchmark
document.) I think we can all be very satisfied with the result, and I
feel that we have accomplished the goal of defining a consensus schema
for the benchmark. As a result, it is time to freeze the schema and
move on. However, new comments related to how I have tried to
accommodate the most recent comments are still very welcome.

Task 2: The benchmark database instance.

A straw proposal for this is now included in the document. In order to
avoid an initial bias, I have described the instance in natural
language, without any tabular representations.

If some tabular representation should be used in this document, the
choice of a particular representation should evolve from the
discussions in this forum.

In my opinion, the transformation of a natural language description of
the db instance to a tabular representation may not be immediately
clear. This is only a problem if we think in terms of tabular
representations. In itself the natural language description is brief.

Tabular representations will of course be used when it is described how
the benchmark queries are expressed in various query languages.

Task 3: The taxonomy of benchmark queries.

A separate document containing a proposal will be posted soon.


********************************************************************
* Notes on the incorporation of recent comments into the benchmark *
* document.                               *
********************************************************************

Scope:
******

***Exclusion of transaction time queries.

It is my evaluation that transaction time data (and queries) should
not be included in this initial version.

Judging from the majority of comments, the general agreement seems to
be that transaction time can be disregarded in the first version. This
is also consistent with the fact that only a minority of the more than
two dozen existing temporal relational data models support both valid
and transaction time.

Some models are capable of treating transaction and valid time queries
in a symmetric fashion. That will become apparent when transaction time
is included.


***Exclusion of nested queries and queries with several references to
the same relation.

It has been pointed out by several contributors that these
restrictions are rather artificial. For that reason, these
restrictions are no longer mentioned in the document.

***Exclusion of updates.

It is certainly true that updates are essential in a temporal data
model. The exclusion of updates in the first version of the benchmark
is not intended to dispute this. Rather, it reflects our cautious
approach where we try to limit the scope where it makes sense. Updates
are easily identified and thus easily excluded.

I propose that we allow updates after regular queries have been
proposed if this turns out to be manageable. Thus, updates will now be
included into the benchmark before the TDB workshop (but not
immediately) if this is practical. I hope this is an acceptable
compromise.

Schema:
*******

***Non-1NF relations.

A temporal relational schema needs not be in 1NF, but I feel that the
non-1NF'ness should be due only to the introduction of time. Put
differently, snapshots should be 1NF relations.

***The dependency Manager --> Dept.

This has been added to the Mgr schema as it appears to introduce more
diversity without adding complexity.

***Naming convention.

Relation instances start with lowercase letters, and relation schemas
(including the attributes) start with uppercase letters.

***New relation schema.

A relation schema, Skills = (Name, Skill), is included. This way, all
relation schemas are in BCNF. Several contributors would like a schema
which is at least in 3NF.

The Attribute Skill is time-varying.

***Adding a Budget attribute to the Mgr schema.

The stated motivation for adding a Budget attribute to the Mgr schema
is to be able to compare time-varying attributes of distinct relations
in a query, e.g., Budget in Mgr and Salary in Emp.

This is an interesting suggestion, and I request further comments on
this. If other contributors feel that this extra attribute allows them
to formulate types of queries that the existing schema does not allow,
it would be very useful to hear about that very soon.

In the current db schema there are two relations (Emp and Skills) both
with time-varying attributes (but Dept and Skill are not easy to
compare meaningfully)...

\documentstyle[11pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% This paper is intended to evolve into the first version of the TSQL
% benchmark.
% The purpose of this draft is to settle on a database instance for
% the already agreed-upon database schema.
% The purpose of the following draft is then to define a taxonomy to
% be used for categorizing the benchmark queries that will follow.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\addtolength{\textwidth}{1.485in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\addtolength{\topmargin}{-.85in}
\addtolength{\textheight}{1.8in}

\newenvironment{prog} { \begin{center} \begin{minipage}{3in}
\begin{tabbing} nnnn\=nnnn\=nnnn\=nnnn\=nnnn\=nnnn\=nnnn\=\kill
}{\end{tabbing} \end{minipage} \end{center}}

\long\def\comment#1{}
\newcommand{\mvd}{\mbox{$\rightarrow \!\!\! \rightarrow \;$}}
\newcommand{\autsp}{$\;\;\;$}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PAPER START
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\title{\Large\bf The TSQL Benchmark \\ DRAFT}
\author{James Clifford \autsp Shashi K.~Gadia \autsp Fabio Grandi
  \autsp Christian S.~Jensen \\ Patrick Kalua \autsp Sunil Nair \autsp
  Edward Robertson \autsp John F.~Roddick \\ Maria Rita Scalas \autsp
  Richard T.~Snodgrass \autsp Abdullah Tansel \autsp Paolo Tiberio
  \autsp Gene Wuu}

%Note that the list of authors is preliminary and may not be accurate!

\date{April 4, 1993}
\maketitle

\section{Introduction}

\subsection{Goal}

The central goal of this document is to provide the temporal database
community with a {\em comprehensive consensus benchmark} for temporal
query languages that is {\em independent} of any existing language
proposal.

This is not a performance benchmark, but is rather a {\em semantic}
benchmark intended to be an aid in evaluating the user-friendliness of
proposals for temporal query languages. Thus, temporal query languages
should ideally be able to express the benchmark queries both
conveniently and naturally.

To obtain a consensus benchmark, researchers in temporal databases
have been invited to participate in this initiative, and each researcher
that has contributed significantly will be a coauthor. The electronic
mail distribution {\tt [e-mail]} is used as the medium for
discussing the benchmark and related issues.

As a consequence of the central goal above, no existing temporal data
models are used or mentioned. The relation schemas of the benchmark
are expressed as sets of attributes, with the temporal aspects being
implicit (of course, specific temporal data models might add explicit
temporal attributes). The contents of the relations are described in
natural language. The benchmark queries are also given only in natural
language.

The benchmark is {\em not} intended to constitute a metric for query
language completeness, and as such it is not a substitute for a
rigorous {\em theoretical} study of expressive powers of various
temporal query languages. Comprehensiveness of the benchmark is
desirable only to ensure that all aspects of query language design are
covered.

It it emphasized that using the benchmark as an advanced, quantitative
scoring system for comparing languages makes little sense. Thus, one
language is not necessarily superior to another just because one is
capable of expressing more benchmark queries than the other. Rather,
the focus is on user-friendliness.

\subsection{Scope}

Within certain boundaries, discussed next, the benchmark is intended
to contain all queries that appear reasonable and that are consistent
with the schema and data of the benchmark.

First, the benchmark is of a semantic nature---in its current form, it
is not aimed at performance comparisons. The intention is to provide a
foundation for comparing the descriptive and operational
characteristics and capabilities of temporal query languages, not
their performance characteristics. Properly extended with additional
relation schemas and a variety of large instances, the benchmark can
also be used for performance comparisons.

Second, a number of restrictions are imposed on which types of queries
are admissible in this version of the benchmark, including the
following.

\begin{itemize}
\item Queries are restricted to valid time only. Transaction-time
  related queries are not explored.

\item Schema evolution and versioning are not considered.

\item Incompleteness is not considered.

\item Recursive queries are not included.

\item General temporal reasoning is beyond the scope of this version
  of the benchmark.

\item Queries involving aggregation facilities are not considered.

\item Only queries are included---updates are not considered.

\comment{
\item Queries involving relations with multivalued dependencies (in
  the snapshot sense) are not explored.}

\comment{
\item User-defined time, including the interaction between
  user-defined time and valid time, is not considered.}

\comment{
\item Queries involving complex data retrieval are excluded.}

\comment{
\item Inheritance at both the schema and data levels is not
  considered.}

\comment{
\item Nested queries are not included.}

\comment{
\item For simplicity, each relation is used only once in each query.}

\end{itemize}

These advanced aspects are excluded solely for pragmatic reasons, and
the exclusion is not meant to imply in any way that the aspects are
not important. The restrictions simply represent an attempt to reduce
the size of the initial benchmark to manageable proportions.

It is emphasized that this benchmark is merely the first in a sequence
of ever-more comprehensive benchmarks. Later benchmarks will relax the
above restrictions on the scope of comprehensiveness imposed on this
benchmark. Specifically, the next version of the benchmark is intended
to include queries that involve aggregation.

\comment{
Specifically, the next version of the benchmark is intended to include
queries that use the same relation more than once, utilize
aggregation, and involve both valid time and user-defined time.}

\section{The Benchmark Database Schema}

\subsection{Criteria}

A suitable database schema for the benchmark should satisfy four
criteria.

\begin{itemize}
\item{} The schema should be natural. That is, it should correspond to
  a reasonable, though possibly greatly simplified, segment of the
  real world. This both reduces the need to explain the model and
  enhances the ability to recognize verball pitfalls in the path to
  the query instances.

\item{} The schema should be simple. This will aid in making the
  benchmark easy to understand. This criterion restricts the number of
  relation schemas and the number of attributes of the individual
  schemas. Additionally, the names of the relations and of the
  attributes should be short, as they will be referenced repeatedly.

  When an extension is proposed, the benefits should be carefully
  compared with the added complexity.

\item{} The schema should allow for comprehensiveness within the
  chosen scope. Using the schema, it should be possible formulate
  queries of all the types that appear reasonable.

  This indicates a need for at least two related relation schemas (for
  natural join queries).

\item{} A schema that has already been used frequently is preferred
  over a new schema. This guarantees that many existing queries can be
  adapted easily to the benchmark.

\item{} For clarity, schema and attribute names must start with
  capital letters.
\end{itemize}

\subsection{The Schema}

The database schema consists of three valid-time relation schemas,
{\tt Emp}, {\tt Skills}, and {\tt Mgr}. In the terminology of the
entity-relationship model, the first schema models an entity set while
the second and third schemas model relationship sets. They are defined
as follows.

Relation {\tt Emp} uses the attributes {\tt Name}, {\tt Salary}, and
{\tt Dept} for recording the relationships between employees,
salaries, and departments. In addition, it contains attributes {\tt
  Gender} and {\tt D-birth} which indicate the gender and date of
birth of an employee. While the salary and department of an employee
varies over time, both {\tt Gender} and {\tt D-birth} are
time-invariant.

Relation {\tt Skills} records the association of employees with skills
via the two attributes {\tt Name} and {\tt Skill}. The skills of an
employee may vary over time. For example, employees are considered to
have the skill ``driving'' only during those interval(s) when they
hold valid licenses.

Relation {\tt Mgr} records the association of employees, as managers,
with departments, and it contains two attributes, {\tt Dept} and {\tt
  Manager}.

Attributes {\tt Name}, {\tt Dept}, {\tt Skill}, and {\tt Manager} are
of type {\tt textString}; attribute {\tt Gender} is one of {\tt F}
(female) and {\tt M} (male); {\tt Salary} is of type {\tt integer};
and {\tt D-birth} is a user-defined time value which may be compared
with valid times.

The relation schemas obey the following {\em snapshot} functional
and multivalued dependencies:

\begin{prog}
For {\tt Emp}: \\
\> {\tt Name} $\rightarrow$ {\tt Salary} \\
\> {\tt Name} $\rightarrow$ {\tt Dept} \\
\> {\tt Name} $\rightarrow$ {\tt Gender} \\
\> {\tt Name} $\rightarrow$ {\tt D-birth} \\
For {\tt Skills}: \\
\> {\tt Name} $\mvd$ {\tt Skill} (and {\tt Name} $\not\rightarrow$
{\tt Skills}) \\
For {\tt Mgr}: \\
\> {\tt Dept} $\rightarrow$ {\tt Manager} \\
\> {\tt Manager} $\rightarrow$ {\tt Dept}
\end{prog}

Note that {\tt Name} is the primary key of {\tt Emp} (it is the only
candidate key). The schema is in snapshot Boyce-Codd normal form.
Schemas {\tt Skills} and {\tt Mgr} are also in snapshot Boyce-Codd
normal form.

The attribute {\tt Manager} of {\tt Mgr} is a foreign key for the
attribute {\tt Name} of {\tt Emp}. Thus, a tuple is allowed to exist
in the {\tt Mgr} relation only if, for each non-empty snapshots of
this tuple, the {\tt Manager} attribute value exists as a {\tt Name}
value of some tuple in the simultaneous snapshot of the {\tt Emp}
relation.

\section{The Benchmark Data}

\subsection{Criteria}

\begin{itemize}
\item{} For simplicity and ease of typing, attribute values should be
  short and salary values should be multiples of \$10,000.

\item{} Transitions (i.e., timestamp values) occur only at the
  beginning of the month, and all dates should be in the time interval
  from 1/1/81 to 12/31/88 (because the digits 8 and 9 are relatively
  hard to distinguish). Time intervals are all specified by the
  inclusive starting and ending events. Also for clarity, relation
  instance names should start with lowercase letters.

\item{} The data should include a ``hole in the history'' of some
  entity. For example, the database may be designed to contain a whole
  in the employment of some employee.

\item{} The data should include asynchronous behavior of attributes.
  For example, the department and salary of employees may change
  independently.
\end{itemize}

\subsection{The Proposed Data}

Three instances, {\tt emp}, {\tt skills}, and {\tt mgr}, are defined
over the {\tt Emp}, {\tt Skills}, and {\tt Mgr} relation schemas,
respectively. The contents of these instances is described below.

There are two employees, Ed and Di.

Ed worked in the Toy department from 2/1/82 to 1/31/87, and in the
Book department from 4/1/87 to the present. His salary was \$20K from
2/1/82 to 5/31/82, then \$30K from 6/1/82 to 1/31/85, then \$40K from
2/1/85 to 1/31/87 and 4/1/87 to the present. Ed is male and was born
on 7/1/55. Several skills are recorded for Ed. He has been qualified
for typing since 4/1/82 and qualified for filing since 1/1/85. He was
qualified for driving from 1/1/82 to 5/1/82 and from 6/1/84 to
5/31/88.

Di worked in and managed the Toy department from 1/1/82 to the
present. Her salary was \$30K from 1/1/82 to 7/31/84, \$40K from
8/1/84 to 8/31/86, then \$50K from 9/1/86 to the present. Di is female
and was born on 10/1/60. Di has been qualified for directing from
1/1/82 to the present.

\end{document}